/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <iostream>

using namespace std;

/*
* Implementation of the two helper classes
*/
Node::Node(PageId pid) {	
	pid  = pid;
	prev = 0;
	next = 0;
}

DoubleLinkedList::DoubleLinkedList() {	
	head = tail = 0;	
	length = 0;
}

int DoubleLinkedList::insert(PageId pid) {	
	if(length == 0) {		
		head = new Node(pid);		
		tail = head;		
		tail->next = 0;		
		head->prev = 0;		
		length == 1;	
	} else {		
		Node* temp = new Node(pid);		
		tail->next = temp;		
		temp->next = 0;		
		temp->prev = tail;		
		tail = temp;		
		length++;	
	}	
	return 0;
}

int DoubleLinkedList::pop(PageId& pid) {	
	pid = tail->pid;	
	Node* temp;	
	if(tail->prev) {		
		temp = tail->prev;	
	} 
	else {return -1;	}	
	delete tail;	
	tail = temp;	
	return 0;
}
int DoubleLinkedList::destructor() {	
	while(head != tail) {		
		Node* temp = tail->prev;		
		delete tail;		
		tail = temp;	
	}	
	delete head;	
	return 0;
}

/* 
* Constructor of a new B+ tree
*/
BTreeIndex::BTreeIndex()
{
	rootPid = -1;	
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    //@done	
	this->mode = mode;	
	if( pf.open(indexname, mode) != 0) {		return RC_FILE_OPEN_FAILED;	}	
	
	if(mode == 'w') {		return 0;	}	

	char buffer[PageFile::PAGE_SIZE];	
	if( pf.read(0, buffer) != 0) {		return RC_FILE_READ_FAILED;	}	
		
	char* iter = &(buffer[0]);	
	memcpy(&rootPid, iter, sizeof(PageId));	
	iter += sizeof(PageId);	
	memcpy(&treeHeight, iter, sizeof(int));	
	
	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	char buffer[PageFile::PAGE_SIZE];	
	char* iter = &(buffer[0]);	
	if( mode == 'w' ) {		
		memset(iter, 0, PageFile::PAGE_SIZE);		
		memcpy(iter, &rootPid, sizeof(PageId));		
		iter += sizeof(PageId);		
		memcpy(iter, &treeHeight, sizeof(PageId));		
		if( pf.write(0, buffer) != 0) {				
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	IndexCursor cursor;	
	
	PageId p;	
	PageId oldPid;	
	BTNonLeafNode nextNode;	
	int midKey;	
	BTNonLeafNode node;	
	BTLeafNode leaf;	
	if( locate(key, cursor) != 0) {		
		cout << "Unable to locate key " << key << endl;	
	}	
	
	if(treeHeight == 1) {		
		leaf.read(cursor.pid, pf);		
		if( leaf.insert(key, rid) != 0) {			
			goto splitNode;		
		}		
		leaf.write(cursor.pid, pf);		
		return 0;	
	}	
	if( leaf.read(cursor.pid, pf) != 0) {		
		char buffer[PageFile::PAGE_SIZE];		
		char* iter = &(buffer[0]);		
		memcpy(iter, &key, sizeof(int));		
		iter += sizeof(int);		
		memcpy(iter, &rid, sizeof(RecordId));		
		leaf.write(cursor.pid, pf);	
	}		

splitNode:	
	BTLeafNode neighbor;		
	int neighborKey;

	leaf.insertAndSplit(key, rid, neighbor, neighborKey);				
	PageId nextNodePtr = leaf.getNextNodePtr();		
	neighbor.setNextNodePtr(nextNodePtr);		
	leaf.setNextNodePtr(pf.endPid());		
	if( leaf.write(cursor.pid, pf) != 0)		{		return RC_FILE_WRITE_FAILED;	}		
	if( neighbor.write(pf.endPid(), pf) != 0)	{		return RC_FILE_WRITE_FAILED;	}		
	
	if(treeHeight == 1) {			
		BTNonLeafNode root;			
		root.initializeRoot(cursor.pid, neighborKey, pf.endPid()-1);			
		if(root.write(pf.endPid(), pf) != 0)	{	return RC_FILE_WRITE_FAILED;	}			
		rootPid = pf.endPid() - 1;			
		treeHeight++;			
		return 0;		
	}		
	int i = 0;		
	do {			
		oldPid = p;			
		list.pop(p);			
		if( node.read(p, pf) != 0) {return RC_FILE_READ_FAILED;	}		

		if(i == 0) {				
			if(node.insert(neighborKey, pf.endPid()-1) == 0) {										
				if( node.write(p, pf) != 0) {	return RC_FILE_WRITE_FAILED;	}								
				break;				
			} 
			else {					
				node.insertAndSplit(neighborKey, cursor.pid, nextNode, midKey);					
				nextNode.write(pf.endPid(), pf);					
				if( node.write(p, pf) != 0) { return RC_FILE_WRITE_FAILED;	}							
			}			
		} 
		else {				
			if(node.insert(midKey, oldPid) == 0) {										
				if( node.write(p, pf) != 0) { return RC_FILE_WRITE_FAILED;}									
				break;				
			} 
			else {					
				node.insertAndSplit(midKey, oldPid, nextNode, midKey);					
				nextNode.write(pf.endPid(), pf);										
				if(p == rootPid) {						
					BTNonLeafNode root;						
					root.initializeRoot(p, midKey, pf.endPid()-1);						
					if(root.write(pf.endPid(), pf) != 0) {	return RC_FILE_WRITE_FAILED;	}						
					rootPid = pf.endPid() - 1;						
					treeHeight++;					
				}					
				if( node.write(p, pf) != 0) {	return RC_FILE_WRITE_FAILED;}					
				break;				
			}			
		}			
		i++;		
	} while(p != rootPid);	

	if( leaf.write(cursor.pid, pf) != 0) { 	return RC_FILE_WRITE_FAILED;	} 		

	list.destructor();	   
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if(treeHeight == 0) {		
		cursor.pid = 1;		
		cursor.eid = 0;		
		treeHeight++;		
		rootPid = 1;	
	} 
	else if(treeHeight == 1) {			
		BTLeafNode root;		
		int eid;

		if( root.read(rootPid, pf) != 0)		{	return RC_FILE_READ_FAILED;	}	
		if( root.locate(searchKey, eid) != 0)	{	return RC_NO_SUCH_RECORD;	}		
		cursor.pid = rootPid;		
		cursor.eid = eid;	
	} 
	else {				
		BTNonLeafNode node;	
		int level = 1;	

		if( node.read(rootPid, pf) != 0)	{	return RC_FILE_READ_FAILED;}				
		while(level < treeHeight) {			
			if(level == 1) {list.insert(rootPid);} 
			else {	list.insert(nextPid);}
			if( node.locateChildPtr(searchKey, nextPid) != 0)	{	return RC_NO_SUCH_RECORD;}			
			if( node.read(nextPid, pf) != 0)					{	return RC_FILE_READ_FAILED;	}			
			level++;		
		}			
		cursor.pid = nextPid;		
		cursor.eid = 0;	
	}    
	return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode node;
	int next;	

	if(node.read(cursor.pid, pf) != 0)				{	return RC_FILE_READ_FAILED;}
	if(node.readEntry(cursor.eid, key, rid) != 0)	{	return RC_INVALID_RID; }	
	if (cursor.eid < node.getKeyCount() - 1)		{	cursor.eid++;	} 
	else {		
		cursor.eid = 0;			
		next = node.getNextNodePtr();		
		if(next == 0)	{	return RC_END_OF_TREE;	}		
		cursor.pid = next;	
	}	    
	return 0;
}
